// easy

// 给定一个二叉树，判断它是否是高度平衡的二叉树，即左右两个子树的高度差的绝对值不超过1

// 解题思路
// 递归遍历二叉树，先递归遍历左右子树，判断左右子树是否平衡，再判断以当前节点为根节点的左右子树是否平衡
// 如果遍历的子树是平衡的，则返回它的高度，否则返回-1
// 只要出现不平衡的子树，则该二叉树一定不是平衡二叉树

function isBalanced(root) {
    function height(root) {
        if (!root) {
            return 0
        }
        let leftHeight = height(root.left)
        let rightHeight = height(root.right)
        if (leftHeight === -1 || rightHeight === -1 || Math.abs(leftHeight - rightHeight) > 1) {
            return -1
        } else {
            return Math.max(leftHeight, rightHeight) + 1
        }
    }
    return height(root) >= 0
}

const root = {
    val: 4,
    left: {
        val: 3,
        left: {
            val: 2,
        },
        right: {
            val: 3.5,
            left: {
                val: 3.1
            }
        },
    },
    right: {
        val: 6,
    },
};

console.log(isBalanced(root))


function getHeight(cur) {
    let stack = []
    let height = 0
    if(cur) {
        stack.push(cur)
    }
    while(stack.length) {
        let node = stack.pop()
        if(!node) {
            stack.pop()
            height--
            continue
        } else {
            stack.push(node)
            stack.push(null)
            node.right && stack.push(node.right)
            node.left && stack.push(node.left)
            height++
        }
    }
    return height
}

console.log(getHeight(root))